package com.just.fun.arithmetic;

import javax.swing.*;

/**
 * 给定一个单链表 L，原节点顺序：L0→L1→…→Ln-1→Ln；编写一个算法，
 * 将节点顺序变更为：L0→Ln→L1→Ln-1→L2→Ln-2→…，即首尾节点交错链接。
 *
 * 实现算法，算法思想：
 *
 * 1. 获取原始链表的中间节点，并断链，将链表分为前后两半；
 *
 * 2. 将后一半链表的节点反转；
 *
 * 3. 将两部分链表交错链接为一条链表返回即可。
 */
public class LinkTest {
    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        listNode.next=new ListNode(2);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(4);
        listNode.next.next.next.next=new ListNode(5);
        reOrderList(listNode);
        System.out.println("重排结果：");
        printVal(listNode);
    }

    /**
     * 定义一个链表类
     */
    private static class ListNode {
       int val;
       ListNode next;
       ListNode(int val){
           this.val=val;
       }
    }

    /**
     * 利用快慢指针算法找到中间节点
     * @param head
     * @return
     */
    public static ListNode findMiddle(ListNode head){
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    /**
     * 将后半部分链表反转
     * 思路1：反转需要三个节点参与，所以这里利用三个临时节点进行反转，最后将原来的头节点next断开，然后设置新的头节点
     * @param secondNode
     * @return
     */
    public static ListNode reverse(ListNode secondNode){
        if(secondNode==null || secondNode.next==null){
            return secondNode;
        }
        ListNode p1=null;
        ListNode p2=secondNode;
        ListNode p3=secondNode.next;
        while (true){
            p2.next=p1;
            if(p3==null){
                break;
            }
            p1=p2;
            p2=p3;
            p3=p3.next;
        }
        secondNode=p2;
        return secondNode;

    }

    /**
     * 链表交叉
     * @param head
     * @param second
     */
    public static void join(ListNode head,ListNode second){
        ListNode p=head;
        while (p!=null && second!=null){
            ListNode n1=p.next;
            ListNode n2=second.next;
            p.next=second;
            if(n1!=null){
                second.next=n1;
            }
            p=n1;
            second=n2;
        }
    }

    /**
     * 算法主体
     * @param listNode
     */
    public static void reOrderList(ListNode listNode){
        if(listNode==null || listNode.next==null){
            return;
        }
        //找到中间节点
        ListNode midNode=findMiddle(listNode);
        //拆分
        ListNode second=midNode.next;
        //断开
        midNode.next=null;
        //反转
        second=reverse(second);
        //交叉合并
        join(listNode,second);
    }

    public static void printVal(ListNode listNode){
        ListNode tmp=listNode;
        while (tmp!=null){
            System.out.print(tmp.val);
            if(tmp.next!=null){
                System.out.print("->");
            }
            tmp=tmp.next;
        }
    }
}
